{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Create a Simple Calculator\n",
    "\n",
    "[The Original Question](https://mp.weixin.qq.com/s/FByt91WRovoaFOAVhK5hKA)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Question\n",
    "\n",
    "Given a mathematical expression with just single digits `0` ~ `9`, plus signs `+`, negative signs `-`, and brackets `(` `)`, evaluate the expression. Assume the expression is properly formed."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example\n",
    "\n",
    "```text\n",
    "Input: - ( 3 + ( 2 - 1 ) )\n",
    "Output: -4\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculator(expression: str) -> int:\n",
    "    # Trim all white-space in raw expression.\n",
    "    expression = expression.replace(' ', '')\n",
    "    \n",
    "    # Create a list (use as a stack) to evaluate calculations.\n",
    "    # To prevent errors if the first character is operator,\n",
    "    # initialize the top element as '0'.\n",
    "    stack = ['0']\n",
    "    \n",
    "    # Traverse all characters in the expression.\n",
    "    for k in expression:\n",
    "        \n",
    "        # If the first character is a digit,\n",
    "        # replace the top elememt of the stack.\n",
    "        if k.isdigit() and stack[-1].isdigit():\n",
    "            stack[-1] = k\n",
    "            pass\n",
    "        \n",
    "        elif k.isdigit():\n",
    "            \n",
    "            # Check operator.\n",
    "            if stack[-1] == '-':\n",
    "                stack.pop()\n",
    "                stack[-1] = str(int(stack[-1]) - int(k))\n",
    "                pass\n",
    "            elif stack[-1] == '+':\n",
    "                stack.pop()\n",
    "                stack[-1] = str(int(stack[-1]) + int(k))\n",
    "                pass\n",
    "            \n",
    "            # No operator before, keep appending.\n",
    "            else:\n",
    "                stack.append(k)\n",
    "                pass\n",
    "            pass\n",
    "        \n",
    "        # Meet the close bracket,\n",
    "        # finish calculating the sub-expression in brackets.\n",
    "        elif k == ')':\n",
    "            temp = stack[-1]\n",
    "            stack.pop()\n",
    "            stack.pop()\n",
    "            if stack[-1] == '-':\n",
    "                stack.pop()\n",
    "                stack[-1] = str(int(stack[-1]) - int(temp))\n",
    "                pass\n",
    "            elif stack[-1] == '+':\n",
    "                stack.pop()\n",
    "                stack[-1] = str(int(stack[-1]) + int(temp))\n",
    "                pass\n",
    "            pass\n",
    "        \n",
    "        # Otherwise, append the character into the stack.\n",
    "        else:\n",
    "            stack.append(k)\n",
    "            pass\n",
    "        \n",
    "        pass\n",
    "    return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-4\n"
     ]
    }
   ],
   "source": [
    "print(calculator('- ( 3 + ( 2 - 1 ) )'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Notes\n",
    "\n",
    "There's a built-in function `eval()` in *Python3* and it can directly calculate string-type expression. This function makes the question meaningless. \n",
    "\n",
    "The source code provided above may not be the best. But by contrast, it is the closest to the original algorithm."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
